#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

//typedef char SLD;
//typedef struct Stack
//{
//    SLD* vim;
//    int max;
//    int num;
//}stack;
//
//void InitStack(stack* p)
//{
//    assert(p);
//    p->vim = NULL;
//    p->max = p->num = 0;
//}
//
//void PushBack(stack* p, SLD x)
//{
//    assert(p);
//    if (p->max == p->num)
//    {
//        p->max = p->max > 0 ? p->max * 2 : 4;
//        p->vim = (SLD*)realloc(p->vim, sizeof(SLD) * p->max);
//    }
//    p->vim[p->num] = x;
//    p->num++;
//}
//
//SLD PopBack(stack* p)
//{
//    assert(p);
//    assert(p->num > 0);
//    return p->vim[--p->num];
//}
//
//void Destory(stack* p)
//{
//    assert(p);
//    free(p->vim);
//    p->vim = NULL;
//    p->num = p->max = 0;
//}
//
//int Size(stack* p)
//{
//    assert(p);
//    return p->num;
//}
//
//bool isValid(char* s) {
//    if (s == NULL)
//    {
//        return false;
//    }
//    int i = 0;
//    stack p;
//    InitStack(&p);
//    while (s[i])
//    {
//        if (s[i] == '(' || s[i] == '{' || s[i] == '[')
//        {
//            PushBack(&p, s[i]);
//        }
//        else if (s[i] == ')' || s[i] == '}' || s[i] == ']')
//        {
//            if (p.num == 0)
//            {
//                return false;
//            }
//            SLD k = PopBack(&p);
//            if ((k == '(' && s[i] != ')') || (k == '{' && s[i] != '}') || (k == '[' && s[i] != ']'))
//            {
//                free(p.vim);
//                return false;
//            }
//        }
//        i++;
//    }
//    free(p.vim);
//    if (p.num == 0)
//    {
//        return true;
//    }
//    return false;
//}
//
//int main()
//{
//    char s[] = "(){}[]";
//    int a = isValid(s);
//    printf("%d\n", a);
//    return 0;
//}

void Sort(int* p1, int* p2)
{
	int index = *p1;
	*p1 = *p2;
	*p2 = index;
}

void InsertSort(int* a, int n)
{
	assert(a);
	for (int i = 0; i < n - 1; i++)
	{
		int max = i;
		for (int x = i; x < n; x++)
		{
			if (a[x] > a[max])
			{
				max = x;
			}
		}
		if (max != i)
		{
			Sort(&a[max], &a[i]);
		}
	}
}

void Print(int* a,int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void ShellSort(int* a, int n)
{
	int gap = n / 2 ;
	while (gap >= 1)
	{
		for (int i = 0; i < n - gap; i++)
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
			//for (int x = i + gap; x < n ; x += gap)
			//{
			//	if (a[min] > a[x])
			//	{
			//		min = x;
			//	}
			//}
			//if (min != i)
			//{
			//	Sort(&a[min], &a[i]);
			//}
		}
		gap /= 2;
	}
}

int main()
{
	int a[] = { 1,2,3,4,5,6,7,8,9 };
	InsertSort(a, 9);
	Print(a, 9);
	ShellSort(a, 9);
	Print(a, 9);
	return 0;
}